def MaxElement(A, n):
    "Find the index of max element of A."
    val, pos = A[0], 0
    for i in range(1, n):
        if A[i] > val:
            val = A[i]
            pos = i
    return val, pos


def FindMax2_1(A, n):
    """
    【常规算法】
    时间复杂度分析：
    W(n)=n-1+n-2=2n-3
    """
    max_val, max_pos = MaxElement(A, n)
    A[n-1], A[max_pos] = A[max_pos], A[n-1]
    val, pos = MaxElement(A, n-1)
    return val


def FindMax2_2_Recur(A, left, right):
    """
    【分治算法】
    时间复杂度分析：
    递归方程：W(n)=2W(n/2)+O(1), W(2)=1
    利用主定理得，W(n)=O(n)
    """
    # 必须分为奇数偶数来讨论，轮空情况。
    n = right-left+1
    assert n >= 2
    if n == 2:
        m1 = max(A[left], A[right])
        m2 = min(A[left], A[right])
        return m1, m2

    if n % 2 == 0:
        q = (left+right)//2
        m11, m12 = FindMax2_2_Recur(A, left, q)
        m21, m22 = FindMax2_2_Recur(A, q+1, right)
        m1 = max(m11, m21)
        m2 = max(m12, m22, min(m11, m21))
        return m1, m2
    else:
        m11, m12 = FindMax2_2_Recur(A, left, right-1)
        temp = A[right]
        if temp > m11:
            m11, m12 = temp, m11
        elif temp > m12:
            m12 = temp
        return m11, m12


def FindMax2_2(A):
    m1, m2 = FindMax2_2_Recur(A, 0, len(A)-1)
    return m2


def Test():
    import random
    n = 4
    A = list(range(n))
    random.shuffle(A)
    print(A)

    val = FindMax2_2(A)
    print(val)

Test()
